# LeetCode 239. 滑动窗口最大值
# https://leetcode.cn/problems/sliding-window-maximum/description/
from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        result = []

        for index, num in enumerate(nums):
            # len(d) > k 弹出队首元素
            if index >= k and index - q[0] >= k:
                q.popleft()

            # 从队尾元素开始 和 num 比较大小
            while q and nums[q[-1]] <= num:
                q.pop()

            q.append(index)
            if index >= k - 1:
                result.append(nums[q[0]])
        return result


# 对拍
class Solution2:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque(nums[:k])
        result = [max(q)]
        for index in range(k, len(nums)):
            q.popleft()
            q.append(nums[index])
            result.append(max(q))
        return result


if __name__ == '__main__':
    nums = [1,3,1,2,0,5]
    k = 3
    result = Solution().maxSlidingWindow(nums, k)
    print(result)
    result2 = Solution2().maxSlidingWindow(nums, k)
    print(result2)
